/*
 * Copyright (C), 2015-2018
 * FileName: Solution5
 * Author:   zhao
 * Date:     2018/10/11 16:53
 * Description: 5. 最长回文子串
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

/**
 * 〈一句话功能简述〉<br>
 * 〈5. 最长回文子串〉
 *
 * @author zhao
 * @date 2018/10/11 16:53
 * @since 1.0.1
 */
public class Solution5 {
  /**************************************
   * 题目
   给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

   示例 1：

   输入: "babad"
   输出: "bab"
   注意: "aba"也是一个有效答案。
   示例 2：

   输入: "cbbd"
   输出: "bb"
   **************************************/

  /**************************************
   *
   * 想法：
   *    1. 暴力破解 找出所有的字符串，判断是不是回文字符串 n3/1
   *    2. 反转字符串 2个字符串之中最长的相交字符串
   *    3. 动态规划
   * 我的做法
   *      超过  %的测试案例
   *
   * 代码执行过程：
   *
   * 总结：
   *
   * ***********************************/

  public String longestPalindromeByDP(String s) {
    if (s == null || s.length() < 1) {
      return "";
    }
    if (s.length() == 1) {
      return s;
    }

    int max = 0;
    String maxStr = "";

    return maxStr;
  }
  /**
   * 暴力破解
   * 超过3%的解法
   * @param s 字符串
   * @return  最大回文字符串
   */
  public String longestPalindromeByForce(String s) {
    if (s == null || s.length() < 1) {
      return "";
    }
    if (s.length() == 1) {
      return s;
    }

    int max = 0;
    String maxStr = "";

    // 双重循环，这样就可以找出所有的字符串了
    for (int i = 0; i < s.length(); i++) {
      for (int j = i; j < s.length(); j++) {
        boolean isPalindrome = true;
        // 这里判断该字符串是不是一个回文字符串
        for (int k = i; k < (i + j) / 2 + 1; k++) {
          char charK = s.charAt(k);
          char charRanK = s.charAt(j + i - k);
          if (charK != charRanK) {
            isPalindrome = false;
            break;
          }
        }

        // 判断回文字符串之后的操作
        if (isPalindrome && j - i > max) {
          maxStr = s.substring(i, j + 1);
          max = j - i;
        }
      }
    }

    if (maxStr.length() < 1) {
      maxStr = s.charAt(0) + "";
    }

    return maxStr;
  }

  /**************************************
   * 比我好的答案 better
   * ***********************************/
  public void better() {
  }

}
